﻿//一、Next permutation

//Implement next permutation, which rearranges numbers into the lexicographically next greater permutation
//of numbers.
//If such arrangement is not possible, it must rearrange it as the lowest possible order(ie, sorted in ascending
//order).
//The replacement must be in - place, do not allocate extra memory.
//Here are some examples.Inputs are in the left - hand column and its corresponding outputs are in the
//right - hand column.
//1, 2, 3 → 1, 3, 2
//3, 2, 1 → 1, 2, 3
//1, 1, 5 → 1, 5, 1

//字典序排列
//把升序的排列（当然，也可以实现为降序）作为当前排列开始，然后依次计算当前排列的下一个字典序排列。
//对当前排列从后向前扫描，找到一对为升序的相邻元素，记为i和j（i < j）。如果不存在这样一对为升序的相邻元素
//，则所有排列均已找到，算法结束；否则，重新对当前排列从后向前扫描，找到第一个大于i的元素k，交换i和k，
//然后对从j开始到结束的子序列反转，则此时得到的新排列就为下一个字典序排列。这种方式实现得到的所有排列是按字典序有序的，
//这也是C++ STL算法next_permutation的思想



//二、Permutation Sequence
//The set[1, 2, 3, ⋯, n] contains a total of n!unique permutations.
//By listing and labeling all of the permutations in order, We get the following sequence(ie, for n = 3) :
//"123"
//"132"
//"213"
//"231"
//"312"
//"321"
//Given n and k, return the kth permutation sequence.
//Note: Given n will be between 1 and 9 inclusive.


#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>
using namespace std;


class Solution{
public:
	//一、两种算法
	vector<int> Nextpermutation(vector<int> a)
	{
		int prev= 0;
		int now = 0;
		int cur = 0;
		int a_len = a.size();
		for (int i = a_len - 1; i > 0; i--)
		{
			if (a[i-1] < a[i])
			{
				prev = i - 1;
				now = i;
				for (int j = a_len - 1; j>prev; j--)
				{
					if (a[j] > a[prev])
					{
						cur = j;
						swap(a[cur], a[prev]);
						reverse(a.begin() + now, a.end());
						return a;
					}
				}
			}
		}
	}
	vector<int> Next_permutation(vector<int> a)  //SLT算法库中提供了next_permutation和prev_permutation
	{
		next_permutation(a.begin(), a.end());
		return a;
	}


	////二、
	//// LeetCode, Permutation Sequence  //不明白
	//// 康托编码，时间复杂度O(n)，空间复杂度O(1)
	//	string getPermutation(int n, int k) {
	//		string s(n, '0');
	//		string result;
	//		for (int i = 0; i < n; ++i)
	//			s[i] += i + 1;
	//
	//			return kth_permutation(s, k);
	//	}
	//private:
	//	int factorial(int n) {
	//		int result = 1;
	//		for (int i = 1; i <= n; ++i)
	//			result *= i;
	//		return result;
	//	}
	//	// seq 已排好序，是第一个排列
	//	template<typename Sequence>
	//	Sequence kth_permutation(const Sequence &seq, int k) {
	//		const int n = seq.size();
	//		Sequence S(seq);
	//		Sequence result;
	//		int base = factorial(n - 1);
	//		--k; // 康托编码从0 开始
	//		for (int i = n - 1; i > 0; k %= base, base /= i, --i) {
	//			auto a = next(S.begin(), k / base);
	//			result.push_back(*a);
	//			S.erase(a);
	//		} 
	//		result.push_back(S[0]); // 最后一个
	//		return result;
	//	}

	int  factorial(int n)
	{
		int ret = 1;
		for (int i = n; i >= 1; i--)
		{
			ret *= i;
		}
		return ret;
	}
	vector<int> Thpermutation(vector<int> a, int n, int k) //自己实现康拓编码
	{
		vector<int> cur(a);
		vector<int> ret;
		int varyk = k;
		int base = 0;
		for (int i = n-1; i >=0; i--)
		{
			int max = factorial(i);
			if (max == varyk)
			{
				cur.reserve(n);
				return cur;
			}
			base = varyk / max;
			while(cur[base] == 0x7fffffff) //用于假删除
			{
				base++;
			}
			ret.push_back(cur[base]);
			cur[base] = 0x7fffffff;
			varyk = varyk%max;	
		}
		return ret;
	}
};



int main()
{
	vector<int> a = { 6, 8, 7, 2, 4, 3 };
	Solution s;
	vector<int> ret1;
	ret1 = s.Nextpermutation(a);
	ret1 = s.Next_permutation(a);

	vector<int> b = { 1, 2, 3, 4 }; //指定序列的第K个全排列
	vector<int >s1;
	s1 = s.Thpermutation(b,4, 10);

	return 0;
}